package com.asia.algorithmcode.monotoneStack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @DESCRIPTION: 85：最大矩形, 继84题后的又一个单调栈，单调栈的经典场景就是找到某个位置左侧(右侧)第一个比它小(大)的元素
 * @USER: wanfu
 * @DATE: 2025/4/15 星期二 10:10
 */
public class MaximalRectangle {


    public static void main(String[] args) {
        char[][] arr = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'},
        };
        System.out.println(new MaximalRectangle().maximalRectangle(arr));
    }

    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        if (n == 0) {
            return 0;
        }
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int[] left = new int[n];
        int[] right = new int[n];

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);
        }
        return res;
    }

    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        if (m == 0 || n == 0) {
            return 0;
        }
        int[][] height = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != '0') {
                    if (i > 0) {
                        height[i][j] = height[i - 1][j] + 1;
                    } else {
                        height[i][j] = 1;
                    }
                }
            }
        }
        int res = 0;
        for (int i = 0; i < m; i++) {
            res = Math.max(res, largestRectangleArea(height[i]));
        }
        return res;
    }

}
